/**
题目:
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

              5
             / \
            4   5
           / \   \
          1   1   5
输出:

2
示例 2:

输入:

              1
             / \
            4   5
           / \   \
          4   4   5
输出:

2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-univalue-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路: 后序遍历 + 分类讨论
*/
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func longestUnivaluePath(root *TreeNode) int {
    res := 0
    helper(&res, root)
    return res
}
func helper(res *int, root *TreeNode)int{
    if root == nil {
        return 0
    }
    left  := helper(res, root.Left)
    right := helper(res, root.Right)
    leftRes, rightRes := 0, 0
    if root.Left != nil  && root.Left.Val == root.Val{
        leftRes +=  left + 1
    }
    if root.Right != nil && root.Right.Val == root.Val{
        rightRes += right + 1
    }
    *res = max(*res, leftRes+rightRes)
    return max(leftRes,rightRes)
}
func max(a, b int)int{
    if a > b{
        return a
    }
    return b
}